package twobranchTree.inorderTraversal;

import java.util.ArrayList;
import java.util.List;

import twobranchTree.preorderTraversal.TreeNode;

/**
 * @Date 2020/2/10
 * @author 王光浩
 * @Description 给出一个二叉树，对它进行中序遍历
 * @Thinking 使用Morris二叉树遍历法。
 *           v复杂度分析：时间复杂度O（2n），空间复杂度O（n）
 */
public class MyMethodTwo {
	public List<Integer> inorderTraversal(TreeNode root) {
		List<Integer> result=new ArrayList<Integer>();
		TreeNode node=root;
		while(node!=null) {
			if(node.left==null) {  //当左子树为空的情况
				result.add(node.val);
				node=node.right;
			}
			else {                //否则将左子树的最后一个节点与根节点形成一个环
				TreeNode inorder=node.left;
				while(inorder.right!=null && inorder.right!=node) {
					inorder=inorder.right;
				}
				if(inorder.right==null) {  //该二叉树的左子树没有与根节点形成一个环
					inorder.right=node;
					node=node.left;
				}
				else {       //该二叉树的左子树与根节点形成了环，左子树已经被遍历过
					result.add(node.val);
					inorder.right=null;  //将二叉树复原
					node=node.right;  //遍历右子树
				}
			}
		}
		return result;
	}
	
	/**
	 * 采用Morris 遍历方法对二叉树进行中序遍历。
	 * @param root
	 * @return
	 */
	public List<Integer> inorderTraversal1(TreeNode root) {
		List<Integer> ret = new ArrayList<Integer>();
		TreeNode node = root;
		while (node != null) {
			if (node.left == null) {
				ret.add(node.val);
				node = node.right;
			} else {
				TreeNode next = node.left;
				while (next.right != null && next.right != node)
					next = next.right;
				if (next.right == null) {
					next.right = node;
					node = node.left;
				} else {
					next.right = null;
					ret.add(node.val);
					node = node.right;
				}
			}
		}
		return ret;
	}
}
